递归和动态规划——斐波拉契数列的递归

Posted on | In ,

【斐波拉契(Febonacci)数列原始问题】
如果一对兔子每月能生1对小兔子，而每对小兔在它出生后的第3个月，又能开始生1对小兔子，假定在不发生死亡的情况下，由1对初生的兔子开始，1年后能繁殖成多少对兔子？
斐波拉契把推算得到的头几个数摆成一串：1，1，2，3，5，8……
F(n)=F(n-1)+F(n-2)

【斐波拉契数列的存在】
甚至可以说，斐波拉契数列无处不在，以下仅举几条常见的例子：
1.杨辉三角对角线上各数之和构成斐波拉契数列 ．
2.多米诺牌（可以看作一个2×1大小的方格）完全覆盖一个n×2的棋盘，覆盖的方案数等于斐波拉契数列。
3.从蜜蜂的繁殖来看，雄峰只有母亲，没有父亲，因为蜂后产的卵，受精的孵化为雌蜂，未受精的孵化为雄峰。人们在追溯雄峰的祖先时，发现一只雄峰的第n代祖先的数目刚好就是斐波拉契数列的第n项fn。
4.钢琴的13个半音阶的排列完全与雄峰第六代的排列情况类似，说明音调也与斐波拉契数列有关。
5.自然界中一些花朵的花瓣数目符合于斐波拉契数列，也就是说在大多数情况下，一朵花花瓣的数目都是3,5,8,13,21,34,……(有6枚是两套3枚;有4枚可能是基因突变)。
6.如果一根树枝每年长出一根新枝，而长出的新枝两年以后，每年也长出一根新枝，那么历年的树枝数，也构成一个斐波拉契数列 ．

【斐波拉契数列的变式】
1.假设农场中成熟的母牛每年只会生1头小牛，且永远不会死。第一年农场只有1头成熟的母牛，从第二年开始，母牛开始生小牛，每只小母牛3年之后成熟又可以生小母牛。给定整数N，求N年之后牛的数量。1,2,3,4,6,9…
F(n)=F(n-1)+F(n-3)
分析：第N年成熟的牛如何估计？所有的牛都不会死，所以第N-1年的牛会活到第N年。第N-3年的牛到了第N年全部成熟，其期间生出的牛肯定都未成熟。
2.帕多瓦数列：1，1，1，2，2，3，4，5，7，9，12，16，21，……这样的数列称为帕多瓦数列。它和斐波拉契数列非常相似，稍有不同的是：每个数都是跳过它前面的那个数，并把再前面的两个数相加而得出的。这个数列可以用另一幅图来表示，它是由一些等边三角形构成的(如下图)。开始的三角形用灰色表示，为了使这些三角形天衣无缝地拼在一起，头三个三角形的边长均为1，其后的两个三角形的边长为2，然后依次是3、4、5、7、9、12、16、2l……等等。
F(n)=F(n-2)+F(n-3),n>=4
2. 冬冬有15块糖，如果每天至少吃3块，吃完为止，那么共有多少种不同的吃法（最后吃的糖可不等于总的粒数）？
如果冬冬有3块糖、4块糖或者5块糖，都只有1种吃法；如果有6块糖，则有2种吃法；如果有7块糖，则有3种吃法；如果有8块糖，则有4种吃法；如果有9块糖，则有6种吃法．
即：
吃糖的粒数：3　4　5　6　7 8 9 10 11 12..．
糖的吃法： 1　1　1　2　3　4　6　 9 　13　19…
这样的数列，它和斐波拉契数列不同的是，每次都是跳过中间的那个数，再把第1、3两个数相加，等于第4个数。它的规律和斐波拉契数列既相似之处又有不同之处．
F(n)=F(n-1)+F(1)，n>=4
3.小明要上楼梯，他每次能向上走一级、两级或三级，如果楼梯有10级，他有几种不同的走法？
这里我们不妨也来研究一下其中的规律：如果楼梯就一级，他有1种走法；如果楼梯有两级，他有2种走法；如果楼梯有三级，他有4种走法；如果有五级楼梯，他有7种走法．
即：
楼梯的级数： 1 2 3 4 5 6 7 8 …
上楼梯的走法：1　2　 4　7　13　24　44　81…
这其中的规律就是，这里从第4个数开始，每一个数都等于它前面的3个数之和。
F(n)=F(n-1)+F(n-2)+F(n-3),n>=4

【求解斐波拉契数列】
1.常规暴力求解Febonacci数列的值，复杂度为O(2^N)。
F(n)=F(n-1)+F(n-2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 利用暴力递归求斐波拉契数列，
* 复杂度o(2^n)
* @param n
* @return
*/
public int f1(int n) {
	if (n < 1) {
		return 0;
	}
	if (n == 1 || n == 2) {
		return 1;
	}
	return f1(n - 1) + f1(n - 2);
}

2.利用矩阵系数求解Febonacci数列，求一个矩阵的N次方，是能在O(logN)时间内解决的问题。
(F(n),F(n-1))=(1,1)*[[1,1],[1,0]]^(n-2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 求矩阵m的p次方
 * @param m
 * @param p
 * @return
 */
public int[][] matrixPower(int[][] m, int p) {
	//设置初始矩阵rst，与m的维度相同，设为单位矩阵，相当于整数中的1
	int[][] rst = new int[m.length][m[0].length];
	for (int i = 0; i < rst.length; i++) {
		rst[i][i] = 1;
	}
	int[][] tmp = m; //复制原m矩阵
	for (; p != 0; p >>=1) { //右移移位相当于除以2
		if ((p&1) != 0) { //p为1
			rst = multiMatrix(rst, tmp);
		}
		tmp = multiMatrix(tmp, tmp);
	}
	return rst;
}
/**
 * 矩阵相乘
 * @param rst
 * @param tmp
 * @return
 */
private int[][] multiMatrix(int[][] m1, int[][] m2) {
	int[][] rst = new int[m1.length][m2[0].length ]; //矩阵m1的行，m2的列
	/*for (int i = 0; i < m2[0].length; i++) {
		for (int j = 0; j < m1.length; j++) {
			for (int k = 0; i < m2.length; i++) {
				rst[i][j] += m1[i][k] * m2[k][j];
			}
		}
	}*/
	for (int i = 0; i < m1.length; i++) {
		for (int j = 0; j < m2[0].length; j++) {
			for (int k = 0; k < m1[0].length; k++) {
				rst[i][j] += m1[i][k] * m2[k][j];
			}
		}
	}
	return rst;
}

另：
如何快速地求解矩阵乘法，其原理与快速求解整数乘法相同。
例：求10^75
1.先将75转换成二进制
(75)10 = (1001011)2 = 2^6+2^3+2^1+2^0=64+8+2+1
2.主要是对指数75进行拆解
10^75 = 10^64*10^8*10^2*10^1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//求解n的m次方
public int pow(int n, int m){
	int tmp = n; //n的一次方
	int rst = 1; //整数1
	while(m != 0){
		//只要遇到1，就累乘现在的幂
		if((m&1) !=  0){
			rst *= temp;
		}
		//每移位一次，幂累乘方一次
		temp = temp * temp;
		m >>= 1;
	}
	return rst;
}